home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gnumake / make360.zoo / dir.c < prev    next >
C/C++ Source or Header  |  1991-08-07  |  10KB  |  402 lines
  1. /* Directory hashing for GNU Make.
  2. Copyright (C) 1988, 1989 Free Software Foundation, Inc.
  3. This file is part of GNU Make.
  4.  
  5. GNU Make is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 1, or (at your option)
  8. any later version.
  9.  
  10. GNU Make is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with GNU Make; see the file COPYING.  If not, write to
  17. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18.  
  19. #include "make.h"
  20.  
  21. #if defined (USGr3) && !defined (DIRENT)
  22. #define DIRENT
  23. #endif /* USGr3 */
  24. #if defined (Xenix) && !defined (SYSNDIR)
  25. #define SYSNDIR
  26. #endif /* Xenix */
  27.  
  28. #if defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__)
  29. #include <dirent.h>
  30. #define direct dirent
  31. #define D_NAMLEN(d) strlen((d)->d_name)
  32. #else /* not POSIX or DIRENT */
  33. #define D_NAMLEN(d) ((d)->d_namlen)
  34. #ifdef USG
  35. #if defined (SYSNDIR)
  36. #include <sys/ndir.h>
  37. #else /* SYSNDIR */
  38. #include "ndir.h"
  39. #endif /* not SYSNDIR */
  40. #else /* not USG */
  41. #include <sys/dir.h>
  42. #endif /* USG */
  43. #endif /* POSIX or DIRENT or __GNU_LIBRARY__ */
  44.  
  45. #if defined (_POSIX_SOURCE)
  46. /* Posix does not require that the d_ino field be present, and some
  47.    systems do not provide it. */
  48. #define REAL_DIR_ENTRY(dp) 1
  49. #else
  50. #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  51. #endif /* _POSIX_SOURCE */
  52.  
  53. /* Hash table of directories.  */
  54.  
  55. struct directory
  56.   {
  57.     struct directory *next;
  58.     char *name;            /* Name of the directory.  */
  59.     struct dirfile **files;    /* Files in this directory.  */
  60.     DIR *dirstream;        /* Stream reading this directory.  */
  61.   };
  62.  
  63. #ifndef    DIRECTORY_BUCKETS
  64. #define DIRECTORY_BUCKETS 23
  65. #endif
  66.  
  67. static struct directory *directories[DIRECTORY_BUCKETS];
  68.  
  69.  
  70. /* Never have more than this many directories open at once.  */
  71.  
  72. #define MAX_OPEN_DIRECTORIES 10
  73.  
  74. static unsigned int open_directories = 0;
  75.  
  76.  
  77. /* Hash table of files in each directory.  */
  78.  
  79. struct dirfile
  80.   {
  81.     struct dirfile *next;
  82.     char *name;            /* Name of the file.  */
  83.     char impossible;        /* This file is impossible.  */
  84.   };
  85.  
  86. #ifndef    DIRFILE_BUCKETS
  87. #define DIRFILE_BUCKETS 1007
  88. #endif
  89.  
  90. /* Find the directory named NAME and return its `struct directory'.  */
  91.  
  92. static struct directory *
  93. find_directory (name)
  94.      register char *name;
  95. {
  96.   register unsigned int hash = 0;
  97.   register char *p;
  98.   register struct directory *dir;
  99.  
  100.   for (p = name; *p != '\0'; ++p)
  101.     HASH (hash, *p);
  102.   hash %= DIRECTORY_BUCKETS;
  103.  
  104.   for (dir = directories[hash]; dir != 0; dir = dir->next)
  105.     if (streq (dir->name, name))
  106.       break;
  107.  
  108.   if (dir == 0)
  109.     {
  110.       /* The directory was not found.  Create a new entry
  111.      for it and start its directory stream reading.  */
  112.       dir = (struct directory *) xmalloc (sizeof (struct directory));
  113.       dir->next = directories[hash];
  114.       directories[hash] = dir;
  115.       dir->name = savestring (name, p - name);
  116.       dir->dirstream = opendir (name);
  117.       if (dir->dirstream == 0)
  118.     /* Couldn't open the directory.  Mark this by
  119.        setting the `files' member to a nil pointer.  */
  120.     dir->files = 0;
  121.       else
  122.     {
  123.       /* Allocate an array of hash buckets for files and zero it.  */
  124.       dir->files = (struct dirfile **)
  125.         xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
  126.       bzero ((char *) dir->files,
  127.          sizeof (struct dirfile) * DIRFILE_BUCKETS);
  128.  
  129.       /* Keep track of how many directories are open.  */
  130.       ++open_directories;
  131.       if (open_directories == MAX_OPEN_DIRECTORIES)
  132.         /* Read the entire directory and then close it.  */
  133.         (void) dir_file_exists_p (dir->name, (char *) 0);
  134.     }
  135.     }
  136.  
  137.   return dir;
  138. }
  139.  
  140. /* Return 1 if the name FILENAME in directory DIRNAME
  141.    is entered in the dir hash table.
  142.    FILENAME must contain no slashes.  */
  143.  
  144. int
  145. dir_file_exists_p (dirname, filename)
  146.      register char *dirname;
  147.      register char *filename;
  148. {
  149.   register unsigned int hash;
  150.   register char *p;
  151.   register struct directory *dir;
  152.   register struct dirfile *df;
  153.   register struct direct *d;
  154.   dir = find_directory (dirname);
  155.  
  156.   if (dir->files == 0)
  157.     /* The directory could not be opened.  */
  158.     return 0;
  159.  
  160.   hash = 0;
  161.   if (filename != 0)
  162.     {
  163.       if (*filename == '\0')
  164.     /* Checking if the directory exists.  */
  165.     return 1;
  166.  
  167.       for (p = filename; *p != '\0'; ++p)
  168.     HASH (hash, *p);
  169.       hash %= DIRFILE_BUCKETS;
  170.  
  171.       /* Search the list of hashed files.  */
  172.  
  173.       for (df = dir->files[hash]; df != 0; df = df->next)
  174.     if (streq (df->name, filename))
  175.       return !df->impossible;
  176.     }
  177.  
  178.   /* The file was not found in the hashed list.
  179.      Try to read the directory further.  */
  180.  
  181.   if (dir->dirstream == 0)
  182.     /* The directory has been all read in.  */
  183.     return 0;
  184.  
  185.   while ((d = readdir (dir->dirstream)) != 0)
  186.     {
  187.       /* Enter the file in the hash table.  */
  188.       register unsigned int newhash = 0;
  189.       register unsigned int i;
  190.  
  191.       if (!REAL_DIR_ENTRY (d))
  192.     continue;
  193.  
  194.       for (i = 0; i < D_NAMLEN(d); ++i)
  195.     HASH (newhash, d->d_name[i]);
  196.       newhash %= DIRFILE_BUCKETS;
  197.  
  198.       df = (struct dirfile *) xmalloc (sizeof (struct dirfile));
  199.       df->next = dir->files[newhash];
  200.       dir->files[newhash] = df;
  201.       df->name = savestring (d->d_name, D_NAMLEN(d));
  202.       df->impossible = 0;
  203.  
  204.       /* Check if the name matches the one we're searching for.  */
  205.       if (filename != 0
  206.       && newhash == hash && streq (d->d_name, filename))
  207.     return 1;
  208.     }
  209.  
  210.   /* If the directory has been completely read in,
  211.      close the stream and reset the pointer to nil.  */
  212.   if (d == 0)
  213.     {
  214.       --open_directories;
  215.       closedir (dir->dirstream);
  216.       dir->dirstream = 0;
  217.     }
  218.  
  219.   return 0;
  220. }
  221.  
  222. /* Return 1 if the file named NAME exists.  */
  223.  
  224. int
  225. file_exists_p (name)
  226.      register char *name;
  227. {
  228.   char *dirend;
  229.   char *dirname;
  230.  
  231. #ifndef    NO_ARCHIVES
  232.   if (ar_name (name))
  233.     return ar_member_date (name) != (time_t) -1;
  234. #endif
  235.  
  236.   dirend = rindex (name, '/');
  237.   if (dirend == 0)
  238.     return dir_file_exists_p (".", name);
  239.  
  240.   dirname = (char *) alloca (dirend - name + 1);
  241.   bcopy (name, dirname, dirend - name);
  242.   dirname[dirend - name] = '\0';
  243.   return dir_file_exists_p (dirname, dirend + 1);
  244. }
  245.  
  246. /* Mark FILENAME as `impossible' for `file_impossible_p'.
  247.    This means an attempt has been made to search for FILENAME
  248.    as an intermediate file, and it has failed.  */
  249.  
  250. void
  251. file_impossible (filename)
  252.      register char *filename;
  253. {
  254.   char *dirend;
  255.   register char *p = filename;
  256.   register unsigned int hash;
  257.   register struct directory *dir;
  258.   register struct dirfile *new;
  259.  
  260.   dirend = rindex (p, '/');
  261.   if (dirend == 0)
  262.     dir = find_directory (".");
  263.   else
  264.     {
  265.       char *dirname = (char *) alloca (dirend - p + 1);
  266.       bcopy (p, dirname, dirend - p);
  267.       dirname[dirend - p] = '\0';
  268.       dir = find_directory (dirname);
  269.       filename = p = dirend + 1;
  270.     }
  271.  
  272.   for (hash = 0; *p != '\0'; ++p)
  273.     HASH (hash, *p);
  274.   hash %= DIRFILE_BUCKETS;
  275.  
  276.   if (dir->files == 0)
  277.     {
  278.       /* The directory was not opened; we must allocate the hash buckets.  */
  279.       dir->files = (struct dirfile **)
  280.     xmalloc (sizeof (struct dirfile) * DIRFILE_BUCKETS);
  281.       bzero ((char *) dir->files, sizeof (struct dirfile) * DIRFILE_BUCKETS);
  282.     }
  283.  
  284.   /* Make a new entry and put it in the table.  */
  285.  
  286.   new = (struct dirfile *) xmalloc (sizeof (struct dirfile));
  287.   new->next = dir->files[hash];
  288.   dir->files[hash] = new;
  289.   new->name = savestring (filename, strlen (filename));
  290.   new->impossible = 1;
  291. }
  292.  
  293. /* Return nonzero if FILENAME has been marked impossible.  */
  294.  
  295. int
  296. file_impossible_p (filename)
  297.      char *filename;
  298. {
  299.   char *dirend;
  300.   register char *p = filename;
  301.   register unsigned int hash;
  302.   register struct directory *dir;
  303.   register struct dirfile *next;
  304.  
  305.   dirend = rindex (filename, '/');
  306.   if (dirend == 0)
  307.     dir = find_directory (".");
  308.   else
  309.     {
  310.       char *dirname = (char *) alloca (dirend - filename + 1);
  311.       bcopy (p, dirname, dirend - p);
  312.       dirname[dirend - p] = '\0';
  313.       dir = find_directo